#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cmath>
#include <cstring>

using namespace std;

class Solution
{
public:
    int maxDistance(vector<vector<int>> &arrays)
    {
        int minIdx = -1, sMinIdx = -1;
        int maxIdx = -1, sMaxIdx = -1;
        int m = arrays.size();
        for (int i = 0; i < m; ++i)
        {
            vector<int> &array = arrays[i];
            int curMin = array[0];
            if (minIdx == -1 ||  curMin < arrays[minIdx][0])
            {
                sMinIdx = minIdx;
                minIdx = i;
            }
            else if (sMinIdx == -1 || curMin < arrays[sMinIdx][0])
            {
                sMinIdx = i;
            }

            int curMax = array.back();
            if (maxIdx == -1 || curMax > arrays[maxIdx].back())
            {
                sMaxIdx = maxIdx;
                maxIdx = i;
            }
            else if (sMaxIdx == -1 || curMax > arrays[sMaxIdx].back())
            {
                sMaxIdx = i;
            }
        }

        if (minIdx != maxIdx)
        {
            return arrays[maxIdx].back() - arrays[minIdx][0];
        }
        // cout << minIdx << " " << sMinIdx << " " << maxIdx << " " << sMaxIdx << "\n";
        return max(
            arrays[maxIdx].back() - arrays[sMinIdx][0],
            arrays[sMaxIdx].back() - arrays[minIdx][0]);
    }
};

int main()
{

    // system("pause");
    return 0;
}
